#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int tmp[50010];
    int reversePairs(vector<int>& record) {
        return merge(record, 0, record.size() - 1);
    }

    int merge(vector<int>& nums, int left, int right)
    {
        if (left >= right) return 0;
        int ret = 0;
        int mid = (left + right) / 2;

        ret += merge(nums, left, mid);
        ret += merge(nums, mid + 1, right);

        int begin1 = left, end1 = mid;
        int begin2 = mid + 1, end2 = right;
        int index = left;
        while (begin1 <= end1 && begin2 <= end2)
        {
            if (nums[begin1] <= nums[begin2])
            {
                tmp[index++] = nums[begin1++];
            }
            else
            {
                ret += end1 - begin1 + 1;
                tmp[index++] = nums[begin2++];
            }
        }

        while (begin1 <= end1) tmp[index++] = nums[begin1++];
        while (begin2 <= end2) tmp[index++] = nums[begin2++];
        for (int i = left; i <= right; i++)
        {
            nums[i] = tmp[i];
        }
        return ret;
    }
};

int main()
{
    vector<int> arr = { 4,6 };
    cout << Solution().reversePairs(arr) << endl;
    return 0;
}

//void _MergeSort(vector<int>& arr, int left, int right, vector<int>& tmp)
//{
//	if (left >= right)
//	{
//		return;
//	}
//	int mid = left + (right - left) / 2;
//	_MergeSort(arr, left, mid, tmp);
//	_MergeSort(arr, mid + 1, right, tmp);
//
//	int begin1 = left, end1 = mid;
//	int begin2 = mid + 1, end2 = right;
//	int index = left;
//	while (begin1 <= end1 && begin2 <= end2)
//	{
//		if (arr[begin1] < arr[begin2])
//		{
//			tmp[index++] = arr[begin1++];
//		}
//		else
//		{
//			tmp[index++] = arr[begin2++];
//		}
//	}
//	while (begin1 <= end1)
//	{
//		tmp[index++] = arr[begin1++];
//	}
//	while (begin2 <= end2)
//	{
//		tmp[index++] = arr[begin2++];
//	}
//	for (int i = left; i <= right; i++)
//	{
//		arr[i] = tmp[i];
//	}
//}
//
//void MergeSort(vector<int>& arr, int size)
//{
//	vector<int> tmp(size);
//	_MergeSort(arr, 0, size - 1, tmp);
//}
//
//void InsertSort(vector<int>& arr, int size)
//{
//	for (int i = 0; i < size - 1; i++)
//	{
//		int end = i;
//		int tmp = arr[end + 1];
//		while (end >= 0)
//		{
//			if (tmp < arr[end])
//			{
//				arr[end + 1] = arr[end];
//				end--;
//			}
//			else
//			{
//				break;
//			}
//		}
//		arr[end + 1] = tmp;
//	}
//}
//
//void ShellSort(vector<int>& arr, int size)
//{
//	int gap = size;
//	while (gap > 1)
//	{
//		gap = gap / 3 + 1;
//		for (int i = 0; i < size - gap; i += gap)
//		{
//			int end = i;
//			int tmp = arr[end + gap];
//			while (end >= 0)
//			{
//				if (tmp < arr[end])
//				{
//					arr[end + gap] = arr[end];
//					end -= gap;
//				}
//				else
//				{
//					break;
//				}
//			}
//			arr[end + gap] = tmp;
//		}
//	}
//}
//
//int main()
//{
//	vector<int> arr = { 6,1,5,8,9,4,2,0,7,3 };
//	//MergeSort(arr, arr.size());
//	//InsertSort(arr, arr.size());
//	ShellSort(arr, arr.size());
//	for (auto& e : arr)
//	{
//		cout << e << ' ';
//	}
//	return 0;
//}